/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace Cobalt.Framework.Graphics
{
	public sealed class DrawList
	{
		private int[] surfaceCount;
		private DrawRecord[][] surfaces;

		private MaterialManager matMgr;

		private Dictionary<int, GeometrySource.IPrerenderHandler> prerenderHandlers 
			= new Dictionary<int, GeometrySource.IPrerenderHandler>();

		public DrawList( IServiceProvider services )
			: this( services, 2048 )
		{
		}

		public DrawList( IServiceProvider services, int initialCapacity )
		{
			if( services == null )
				throw new ArgumentNullException( "services" );

			IMaterialService matSvc = (IMaterialService)services.GetService( typeof( IMaterialService ) );
			if( matSvc == null )
				throw new ArgumentException( "IMaterialService is missing." );

			matMgr = matSvc.MaterialManager;
			if( matMgr == null )
				throw new ArgumentException( "IMaterialService is missing manager object." );

			surfaceCount = new int[Material.NumLayers];
			surfaces = new DrawRecord[Material.NumLayers][];

			for( int i = 0; i < surfaces.Length; i++ )
				surfaces[i] = new DrawRecord[initialCapacity];

			sortKeys = new SortKey[initialCapacity];
		}

		#region Sorting
		[StructLayout( LayoutKind.Explicit, Size = 8 )]
		private struct SortKey
		{
			[FieldOffset( 0 )]
			public ulong SortValue;

#if XBOX
			[FieldOffset( 0 )]
			public ushort LayerSort;
			[FieldOffset( 2 )]
			public ushort MatrixSort;
			[FieldOffset( 4 )]
			public ushort SourceSort;
			[FieldOffset( 6 )]
			public ushort SurfaceSort;
#else
			[FieldOffset( 6 )]
			public ushort LayerSort;
			[FieldOffset( 4 )]
			public ushort MatrixSort;
			[FieldOffset( 2 )]
			public ushort SourceSort;
			[FieldOffset( 0 )]
			public ushort SurfaceSort;
#endif

		}

		private SortKey[] sortKeys;

		private unsafe void DoSort( DrawRecord[] surfaces, SortKey* keys, int left, int right )
		{
			while( left < right )
			{
				int l = left;
				int r = right;

				ulong pivot = keys[(l + r) >> 1].SortValue;

				while( l <= r )
				{
					while( keys[l].SortValue < pivot )
						l++;

					while( pivot < keys[r].SortValue )
						r--;

					if( l <= r )
					{
						if( l != r )
						{
							SortKey key = keys[l];
							keys[l] = keys[r];
							keys[r] = key;

							DrawRecord rec = surfaces[l];
							surfaces[l] = surfaces[r];
							surfaces[r] = rec;
						}

						l++;
						r--;
					}
				}

				if( (r - left) <= (right - l) )
				{
					if( left < r )
						DoSort( surfaces, keys, left, r );

					left = l;
				}
				else
				{
					if( l < right )
						DoSort( surfaces, keys, l, right );

					right = r;
				}
			}
		}

		private unsafe void GenerateSortKeys( int layer )
		{
			fixed( int* layerSorts = &matMgr.layerSortIndices[layer][0] )
			fixed( SortKey* kBegin = &sortKeys[0] )
			{
				SortKey* kEnd = kBegin + surfaceCount[layer];
				SortKey* k = kBegin;

				foreach( DrawRecord rec in surfaces[layer] )
				{
					if( k == kEnd )
						break;

					k->LayerSort = unchecked( (ushort)layerSorts[rec.Material.sortOrder] );
					k->MatrixSort = unchecked( (ushort)rec.ModelMatrixID );
					k->SourceSort = unchecked( (ushort)rec.surface.source.sortId );
					k->SurfaceSort = unchecked( (ushort)rec.surface.surfaceSort );

					k++;
				}
			}
		}

		public unsafe void Sort()
		{
			for( int i = 0; i < Material.NumLayers; i++ )
			{
				if( surfaceCount[i] == 0 )
					continue;

				GenerateSortKeys( i );
				fixed( SortKey* keys = &sortKeys[0] )
					DoSort( surfaces[i], keys, 0, surfaceCount[i] - 1 );
			}
		}

		#endregion

		#region Prerender
		public void Prerender( ShadingContext context, Material.Layer layer )
		{
			PerformanceCounters pc = context.PerformanceCounters;

			int surfaceCount = this.surfaceCount[(int)layer];
			DrawRecord[] surfaces = this.surfaces[(int)layer];

			int lastMtx = -1;
			GeometrySource lastSrc = null;
			GeometrySource.IPrerenderHandler helper = null;

			for( int e, s = 0; s < surfaceCount; s = e )
			{
				GeometrySource src = surfaces[s].surface.source;
				Material mat = surfaces[s].Material;

				int mtx = surfaces[s].ModelMatrixID;

				for( e = s + 1; e < surfaceCount; e++ )
				{
					if( surfaces[e].surface.source != src ||
						surfaces[e].Material != mat ||
						surfaces[e].ModelMatrixID != mtx )
						break;
				}

				if( src != lastSrc )
				{
					if( helper != null )
					{
						helper.EndPreRender( lastSrc );
						helper = null;
					}

					if( !prerenderHandlers.TryGetValue( src.sortId, out helper ) )
					{
						helper = src.CreatePrerenderHandler();
						prerenderHandlers.Add( src.sortId, helper );
					}

					if( helper != null )
						helper.BeginPrerender( src );

					lastSrc = src;
				}

				if( mtx != lastMtx )
				{
					context.Model = matList[mtx];
					lastMtx = mtx;
				}

				if( helper != null )
					helper.Prerender( src, surfaces, s, e - s, context );
			}

			if( helper != null )
				helper.EndPreRender( lastSrc );
		}

		public void Prerender( ShadingContext context )
		{
			for( int i = 0; i < Material.NumLayers; i++ )
				Prerender( context, (Material.Layer)i );
		}
		#endregion

		#region List Management
		private sealed class MatrixComparer : IEqualityComparer<Matrix>
		{
			#region IEqualityComparer<Matrix> Members

			public bool Equals( Matrix x, Matrix y )
			{
				return x == y;
			}

			public int GetHashCode( Matrix obj )
			{
				return (obj.M11 + obj.M22 + obj.M33).GetHashCode();
			}

			#endregion
		}

		private List<Matrix> matList = new List<Matrix>();
		private Dictionary<Matrix, int> matDict = new Dictionary<Matrix, int>( new MatrixComparer() );

		public void Reset()
		{
			for( int i = 0; i < surfaces.Length; i++ )
				Array.Clear( surfaces[i], 0, surfaceCount[i] );

			Array.Clear( surfaceCount, 0, surfaceCount.Length );

			matList.Clear();
			matDict.Clear();
		}

		public int RegisterMatrix( ref Matrix mat )
		{
			int ret;
			if( !matDict.TryGetValue( mat, out ret ) )
			{
				ret = matList.Count;
				matList.Add( mat );
				matDict.Add( mat, ret );
			}
			return ret;
		}

		public int RegisterMatrix( Matrix mat )
		{
			return RegisterMatrix( ref mat );
		}

		private const int GrowBy = 512;
		private void EnsureSpace( ref DrawRecord[] surfaces, int surfaceCount, int spaceNeeded )
		{
			int growAmount = surfaceCount + spaceNeeded - surfaces.Length;

			if( growAmount > 0 )
			{
				System.Diagnostics.Trace.WriteLine( "Growing Render3DViewCommand.surfaces.", "Performance.GC" );
				
				int newLen = surfaces.Length + (growAmount / GrowBy + 1) * GrowBy;
				Array.Resize( ref surfaces, newLen );

				if( surfaces.Length > sortKeys.Length )
					sortKeys = new SortKey[surfaces.Length];
			}
		}

		public void AddDrawSurface( GeometrySurface surface, Material material, int modelMatrixId )
		{
			if( surface == null )
				throw new ArgumentNullException( "surface" );
			if( material == null )
				throw new ArgumentNullException( "material" );
			if( modelMatrixId < 0 || modelMatrixId >= matList.Count )
				throw new ArgumentException( "Invalid Matrix ID", "modelMatrixId" );

			for( int i = 0; i < surfaces.Length; i++ ) //surfaces.Length == Material.NumLayers
			{
				if( material.layers[i] == null )
					continue;

				EnsureSpace( ref surfaces[i], surfaceCount[i], 1 );
				surfaces[i][surfaceCount[i]++] = new DrawRecord( surface, material, modelMatrixId );
			}
		}

		public void AddDrawSurface( GeometrySurface surface, Material material, Matrix modelMatrix )
		{
			AddDrawSurface( surface, material, RegisterMatrix( ref modelMatrix ) );
		}

		public void AddDrawSurface( GeometrySurface surface, Material material, ref Matrix modelMatrix )
		{
			AddDrawSurface( surface, material, RegisterMatrix( ref modelMatrix ) );
		}
		#endregion

		#region Drawing

		private void RenderSurfaces( ShadingContext context, int layer )
		{
			PerformanceCounters pc = context.PerformanceCounters;
			
			int surfaceCount = this.surfaceCount[layer];
			DrawRecord[] surfaces = this.surfaces[layer];

			int lastMtx = -1;
			GeometrySource lastSrc = null;
			GeometrySource.IPrerenderHandler prerenderHandler = null;

			for( int e, s = 0; s < surfaceCount; s = e )
			{
				GeometrySource src = surfaces[s].surface.source;
				Material mat = surfaces[s].Material;
				LayerShader sh = mat.layers[layer];

				int mtx = surfaces[s].ModelMatrixID;

				for( e = s + 1; e < surfaceCount; e++ )
				{
					if( surfaces[e].surface.source != src ||
						surfaces[e].ModelMatrixID != mtx )
						break;

					if( surfaces[e].Material != mat &&
						surfaces[e].Material.layers[layer] != sh )
						break;
				}

				if( src != lastSrc )
				{
					prerenderHandlers.TryGetValue( src.sortId, out prerenderHandler );

					if( lastSrc != null )
						lastSrc.End( context, prerenderHandler );
					src.Begin( context, prerenderHandler );
					lastSrc = src;
				}

				if( mtx != lastMtx )
				{
					context.Model = matList[mtx];
					lastMtx = mtx;
				}

				int numSurfs = e - s;

				context.currentMaterial = mat;
				context.currentMaterialLayer = sh;

				int numPasses = sh.Begin( context );
				for( int i = 0; i < numPasses; i++ )
				{
					sh.BeginPass( i, context );
					src.DrawSurfaces( surfaces, s, numSurfs, context, prerenderHandler );
					sh.EndPass( i, context );
				}
				sh.End( context );

				pc.layerBegins++;
				pc.layerPassBegins += numPasses;
				pc.surfacesDrawn += numSurfs;
				pc.surfacesDrawCount += numSurfs * numPasses;
			}

			if( lastSrc != null )
				lastSrc.End( context, prerenderHandler );

			context.currentMaterial = null;
			context.currentMaterialLayer = null;
		}

		public void Render( ShadingContext context, Material.Layer layer )
		{
			RenderSurfaces( context, (int)layer );
		}

		#endregion
		
	}

	public struct DrawRecord
	{
		internal Material Material;
		internal int ModelMatrixID;

		internal GeometrySurface surface;
		public GeometrySurface Surface
		{
			get { return surface; }
		}

		public int PrerenderParam;

		internal DrawRecord( GeometrySurface surface, Material material, int modelMatrixID )
		{
			this.surface = surface;
			this.Material = material;
			this.ModelMatrixID = modelMatrixID;

			this.PrerenderParam = 0;
		}
	}
}
